package com.hy;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:只出现一次数字
 *
 * 给你一个整数数组nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。
 * 请你找出并返回那个只出现了一次的元素。
 *
 *
 *
 * 示例 1：
 * 输入：nums = [2,2,3,2]
 * 输出：3
 *
 * 示例 2：
 * 输入：nums = [0,1,0,1,0,1,100]
 * 输出：100
 *
 * 提示：
 * 1 <= nums.length <= 3 * 104
 * -231 <= nums[i] <= 231 - 1
 * nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
 *
 *
 * 进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 *
 * author: Mr.Du
 * Date: 2022/11/21
 * Time: 16:29
 */
public class SingleNumberII {
    
    public static void main(String[] args) {
        SingleNumberII numberII = new SingleNumberII();
        int res = numberII.singleNumber(new int[]{2, 2, 2, 5, 4, 4, 4});
        System.out.println(res);
        res = numberII.singleNumber1(new int[]{2, 2, 2, 5, 4, 4, 4});
        System.out.println(res);
        res = numberII.singleNumber2(new int[]{2, 2, 2, 5, 4, 4, 4});
        System.out.println(res);
    }
    
    /**
     * 思想：出现三次的和只出现一次，出现三次的二进制每位相加等于3或等于0，对3取模等于0，只有出现一次的，它和出现
     * 三次的每个二进制位相加对3取模要么等于0或1，那么我们只需要计算取模等于1的，把它复位即可
     *
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        int tmp = 0;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            for (int j : nums) {
                // 统计一趟每个二进制位之和
                tmp += (j >> i) & 1;
            }
            if (tmp % 3 != 0) {
                // 异或操作：就是将二进制位按原来数字二进制复位
                res |= (1 << i);
            }
            tmp = 0;
        }
        return res;
    }
    
    /**
     * 排序操作
     *
     * @param nums
     * @return
     */
    public int singleNumber1(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        for (int i = 0; i < nums.length - 1; ) {
            if (nums[i] == nums[i + 1]) {
                res = nums[i];
                i += 3;
            } else {
                return nums[i];
            }
        }
        return nums[nums.length - 1];
    }
    
    /**
     * map操作
     *
     * @param nums
     * @return
     */
    public int singleNumber2(int[] nums) {
        
        Map<Integer, Integer> mp = new HashMap<>();
        for (int i : nums) {
            mp.put(i, mp.getOrDefault(i, 0) + 1);
        }
        
        for (Map.Entry<Integer, Integer> e : mp.entrySet()) {
            if (e.getValue() == 1) {
                return e.getKey();
            }
        }
        return -1;
        
    }
}
